package com.wxh.algorithm;

import java.util.HashSet;
import java.util.Set;

/**
 * @ClassName: AlgorithmTestQuestion
 * @Description: 算法试题
 * @Author wxh
 * @Date: 2021/3/16 16:34
 * @Version V1.0.0
 * @Since 1.8
 */
public class AlgorithmTestQuestion {

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 0, 2, 5, 3};
        System.out.println("repeat = " + findRepeatNumber(nums));

        System.out.println("-----------------华丽分割线-----------------------");

        String str = "We are happy.";
        System.out.println("replaceSpace(str) = " + replaceSpace(str));
    }

    /**
     * 问题：数组中重复的数字
     * @param nums 数组参数
     * @return int
     */
    public static int  findRepeatNumber(int[] nums){
        /**
         * 初始化集合为空集合，重复的数字 repeat = -1
         *  遍历数组中的每个元素：
         * 将该元素加入集合中，判断是否添加成功
         * 如果添加失败，说明该元素已经在集合中，因此该元素是重复元素，将该元素的值赋给 repeat，并结束遍历
         * 返回 repeat
         * 时间复杂度：O(n)O(n), 空间复杂度：O(n)O(n)
         */
        // 存放重复的数字
        Set<Integer> set = new HashSet<>(16);
        // 表示重复数字的标识位
        int repeat = -1;
        for(int num : nums){
            // 添加失败，表示是重复数字
            if(!set.add(num)){
                repeat = num;
                break;
            }
        }
        return repeat;
    }

    /**
     * 问题：请实现一个函数，把字符串 s 中的每个空格替换成"%20"
     * @param str 字符串参数
     * @return String
     */
    public static String replaceSpace(String str){
        /**
         * 创建字符数组 array，其长度为 length * 3
         * 初始化 size 为 0，size 表示替换后的字符串的长度
         * 从左到右遍历字符串 s
         * 获得 s 的当前字符 c
         * 如果字符 c 是空格，则令 array[size] = '%'，array[size + 1] = '2'，array[size + 2] = '0'，并将 size 的值加 3
         * 如果字符 c 不是空格，则令 array[size] = c，并将 size 的值加 1
         * 遍历结束之后，size 的值等于替换后的字符串的长度，从 array 的前 size 个字符创建新字符串，并返回新字符串
         * 时间复杂度：O(n)O(n), 空间复杂度：O(n)O(n)
         */
        int length = str.length();
        // 存放字符串中的字符串和替换的字符
        char[] chars = new char[length * 3];
        // 存放替换后的字符的长度
        int size = 0 ;
        // 遍历字符串
        for (int i = 0; i < length; i++) {
            // 取出每一个字符
            char ch = str.charAt(i);
            // 是空格,替换为%20
            if(ch == ' '){
                chars[size++] = '%';
                chars[size++] = '2';
                chars[size++] = '0';
            }else{
                chars[size++] = ch;
            }
        }
        // 以新的长度构建字符串
        String newStr = new String(chars, 0, size);
        return newStr;
    }
}
